/*
 * @Author: szx
 * @Date: 2022-05-02 13:22:37
 * @LastEditTime: 2022-05-02 14:03:30
 * @Description:
 * @FilePath: \leetcode\1300-1399\1305\1305.js
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {number[]}
 */
var getAllElements = function (root1, root2) {
    const arr1 = [];
    const arr2 = [];
    const makeArr = (root, arr) => {
        if (!root) return;
        arr.push(root.val);
        if (root.left) makeArr(root.left, arr);
        if (root.right) makeArr(root.right, arr);
    };
    makeArr(root1, arr1);
    makeArr(root2, arr2);
    let i = 0,
        j = 0;
    const res = [];
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] < arr2[j]) {
            res.push(arr1[i]);
            i++;
        } else {
            res.push(arr2[j]);
            j++;
        }
    }
    if (i == arr1.length) return res.concat(arr2.slice(j));
    else return res.concat(arr1.slice(i));
};

var getAllElements = function (root1, root2) {
    const bst1 = new BSTIterator(root1);
    const bst2 = new BSTIterator(root2);
    const res = [];
    while (bst1.hasNext() && bst2.hasNext()) {
        if (bst1.peek() < bst2.peek()) res.push(bst1.next());
        else res.push(bst2.next());
    }
    while (bst1.hasNext()) res.push(bst1.next());
    while (bst2.hasNext()) res.push(bst2.next());
    return res;
};
var BSTIterator = function (root) {
    this.cur = root;
    this.stack = [];
};

BSTIterator.prototype.next = function () {
    while (this.cur) {
        this.stack.push(this.cur);
        this.cur = this.cur.left;
    }
    this.cur = this.stack.pop();
    const res = this.cur.val;
    this.cur = this.cur.right;
    return res;
};

BSTIterator.prototype.peek = function () {
    return this.stack[this.stack.length - 1];
};

BSTIterator.prototype.hasNext = function () {
    return this.cur != null || this.stack.length;
};
